from idlelib.tree import TreeNode
from typing import List
import sys


def replace_char(string, char, index):
    string = list(string)
    string[index] = char
    return ''.join(string)


"""
    @:author Training
    @:description  目标和  给数组中的数添加符号(+,-) 使得最终值为 目标值:S  返回方法数
    @:think 枚举: 每一个数据进行 + - 两个符号的枚举  当枚举的数据量和目标数组的数据量等于时 判断其和是否为S 若为S 则value +1
            // 执行对象中的findTargetSumWays函数
    @:param  
    @:return {}
"""


class Solution:
    def __init__(self):
        self.value = 0

    def findTargetSumWays(self, nums: List[int], S: int) -> int:
        self.calculate(nums, 0, 0, S)
        return self.value

    def calculate(self, nums: List[int], i: int, sum: int, S: int):
        if len(nums) == i:
            if sum == S:
                self.value += 1
                return
        else:
            self.calculate(nums, i + 1, sum + nums[i], S)
            self.calculate(nums, i + 1, sum - nums[i], S)


# a = Solution()
# res = a.findTargetSumWays([27, 33, 4, 43, 31, 44, 47, 6, 6, 11, 39, 37, 15, 16, 8, 19, 48, 17, 18, 39], 24)
# print(res)
'''
    @:author Training
    @:description 全排列问题
    @:think 回溯算法
    @:param
    @return {}
'''
"""
    result = []
    def backtrack(路径, 选择列表):
        if 满⾜结束条件:
            result.add(路径)
            return
            
        for 选择 in 选择列表:
            # 做选择
            将该选择从选择列表移除
            路径.add(选择)
            backtrack(路径, 选择列表)
            # 撤销选择
            路径.remove(选择)
            将该选择再加⼊选择列表
"""


class Solution:
    def __init__(self):
        self.solution_result = []  # 最终结果

    def permute(self, nums: List):
        # 记录路径
        track = []  # 暂存路径
        self.backtrack(nums, track)
        return self.solution_result

    def backtrack(self, nums, track):
        if len(track) == len(nums):
            self.solution_result.append(track.copy())
            return
        for k in nums:
            try:
                track.index(k)
            except:
                track.append(k)
                self.backtrack(nums, track)
                track.pop()


'''
回溯
n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
皇后之间横排,竖排,斜排都能攻击, 所以不能存在其他皇后
如: 4皇后输出：[
 [".Q..",  // 解法 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // 解法 2
  "Q...",
  "...Q",
  ".Q.."]
]
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/n-queens
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
'''


class Solution2:
    def __init__(self):
        self.result = []

    def solveNQueens(self, n: int) -> List[List[str]]:
        track = ["." * n] * n
        self.backtrack(track, 0)
        return self.result

    def backtrack(self, track: list, row: int):
        if len(track) == row:
            self.result.append(track.copy())
            return
        n = len(track[row])

        for i in range(n):
            if not self.isValid(track, row, i):
                continue

            track[row] = replace_char(track[row], "Q", i)
            self.backtrack(track, row + 1)
            track[row] = replace_char(track[row], ".", i)

    def isValid(self, track, row, col):
        n = len(track)
        for i in range(n):
            if track[i][col] == "Q":
                return False

        for i in range(n):
            if row + i < n and col + i < n and track[row + i][col + i] == "Q":
                return False
            elif row - i >= 0 and col - i >= 0 and track[row - i][col - i] == "Q":
                return False

        for i in range(n):
            if row + i < n and col - i >= 0 and track[row + i][col - i] == "Q":
                return False
            elif row - i >= 0 and col + i < n and track[row - i][col + i] == "Q":
                return False

        return True


'''

DFS 深度遍历

给定一个二叉树，返回所有从根节点到叶子节点的路径。

说明: 叶子节点是指没有子节点的节点。

示例:

输入:

   1
 /   \
2     3
 \
  5

输出: ["1->2->5", "1->3"]

解释: 所有根节点到叶子节点的路径为: 1->2->5, 1->3

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-tree-paths
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

'''
"""
    @:author Training
    @:description  通过深度优先遍历,遍历所有的路径数据
    @:think DFS
    @:param root 二叉树 
    @:return {result:list}
"""


class Solution3:
    def __init__(self):
        self.result = []

    def binaryTreePaths(self, root: TreeNode) -> List[str]:
        track = ""
        self.backtrack(root, track)
        return self.result

    def backtrack(self, root, track):
        if not root:
            return
        val = root.val
        v_str = "->" + str(val)
        track += v_str
        if (not root.left) and (not root.right):
            track = track[2:]
            self.result.append(track)
            return

        self.backtrack(root.left, track)
        self.backtrack(root.right, track)
        track = track[0:len(track) - len(v_str)]


"""
    @:author Training
    @:description  752. 打开转盘锁
        你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有10个数字： '0', '1', '2', '3', '4', '5', '6', '7', '8', '9' 。每个拨轮可以自由旋转：例如把 '9' 变为  '0'，'0' 变为 '9' 。每次旋转都只能旋转一个拨轮的一位数字。
    
        锁的初始数字为 '0000' ，一个代表四个拨轮的数字的字符串。
        
        列表 deadends 包含了一组死亡数字，一旦拨轮的数字和列表里的任何一个元素相同，这个锁将会被永久锁定，无法再被旋转。
        
        字符串 target 代表可以解锁的数字，你需要给出最小的旋转次数，如果无论如何不能解锁，返回 -1。
        
        来源：力扣（LeetCode）
        链接：https://leetcode-cn.com/problems/open-the-lock
        著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
    @:think 先忽略所有限制,每一个点有8种可能: 比如: 0000 ->
        1000,0100,0010,0001,9000,0900,0090,0009
    @:param  
    @:return {}
"""


class OpenLock:
    def nextPassword(self, now):
        length = len(now)
        res = []
        for i in range(length):
            item = now[i]
            if item == '0' or item == '9':
                res.append(replace_char(now, '9' if item == '0' else '8', i))  # -1
                res.append(replace_char(now, '1' if item == '0' else '0', i))  # +1
            else:
                res.append(replace_char(now, str(int(item) + 1), i))
                res.append(replace_char(now, str(int(item) - 1), i))
        return res

    # 优化版
    def openLock(self, deadends, target):
        deadends = set(deadends)
        root = "0000"
        queue = {root}
        queue1 = {target}
        visited = {root}
        step = 0
        while len(queue) > 0 and len(queue1) > 0:
            temp = set()
            for cur in queue:
                print(cur)
                if cur in queue1:
                    return step

                if cur in deadends:
                    continue
                visited.add(cur)

                res = self.nextPassword(cur)
                for k in res:
                    temp.add(k)
            step += 1
            queue = queue1
            queue1 = temp
        return -1
    # 原版
    # def openLock(self, deadends, target):
    #     deadends = set(deadends)
    #     root = "0000"
    #     queue = [root]
    #     visited = {root}
    #     step = 0
    #     while len(queue) > 0:
    #         length = len(queue)
    #         for i in range(length):
    #             cur = queue.pop(0)
    #             if cur == target:
    #                 return step

    #             if cur in deadends:
    #                 continue

    #             res = self.nextPassword(cur)
    #             for k in res:
    #                 if not k in visited:
    #                     visited.add(k)
    #                     queue.append(k)
    #         step += 1
    #     return -1


"""
    @:author Training
    @:description  从排序数组中查找一个数 返回下标
    @:think 二分搜索
    @:param  
    @:return 
"""


def getNumber(nums, target):
    left = 0
    right = len(nums) - 1
    while left <= right:
        mid = int(left + (right - left) / 2)
        item = nums[mid]
        if item == target:
            return mid
        elif item < target:
            left = mid + 1
        elif item > target:
            right = mid - 1
    return -1


def getLeftNumber(nums, target):
    left = 0
    right = len(nums)
    while left < right:
        mid = int(left + (right - left) / 2)
        item = nums[mid]
        if item == target:
            right = mid  # 这里需要注意
        elif item < target:
            left = mid + 1
        elif item > target:
            right = mid
    return left if nums[left] == target or left < right else -1


def getRightNumber(nums, target):
    left = 0
    right = len(nums)
    while left < right:
        mid = int(left + (right - left) / 2)
        item = nums[mid]
        if item == target:
            left = mid + 1  # 这里需要注意
        elif item < target:
            left = mid + 1
        elif item > target:
            right = mid - 1

    return right if nums[right] == target or left < right else -1


"""
    @:author Training
    @:description  77. 组合
        给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。
        示例: 
            输入: n = 4, k = 2
            输出:
            [
              [2,4],
              [3,4],
              [2,3],
              [1,2],
              [1,3],
              [1,4],
            ]
    @:think 动态规划
        如 上
        先不管限制条件, 1 能延延展出: 11,12,13,14  2能延展出: 21,22,23,24 以此类推
        然后再加上限制条件(代码注释中有)
    @:param  
    @:return 
"""


class Combine:
    def __init__(self):
        self.result = []

    def combine(self, n, k):
        track = []
        self.backtrack(track, n, k)
        return self.result

    def backtrack(self, track, n, k):
        if len(track) == k:  # 数据的大小
            self.result.append(track.copy())
            return
        for i in range(n):
            item = i + 1
            if not self.isValid(track, item):  # 筛选有用条件
                continue
            track.append(item)
            self.backtrack(track, n, k)
            track.pop()

    # 筛选有用条件
    # 根据题目要求, 找到有用规律
    # 1. 单条不能有重复的数据 如[1,1],[2,2]等
    # 2. 不能有相同的数据 如: [1,2],[2,1]等
    # 所以得出规律 : 单条数据中, 下标越大的数据都比前面的数据大
    # 比如 n = 4 k = 2 的结果: [1,2],[1,3],[1,4],[2,3],[2,4],[3,4]
    def isValid(self, nums, cur):
        le = len(nums) - 1  # 当数据为0条的时候不予判断
        # 规律
        if le >= 0 and nums[le] >= cur:
            return False
        return True


"""
    @:author Training
    @:description  76 最小覆盖子串
        给你一个字符串 S、一个字符串 T 。请你设计一种算法，可以在 O(n) 的时间复杂度内，从字符串 S 里面找出：包含 T 所有字符的最小子串。
    @:think 使用滑动窗口
    @:param  
    @:return 
"""


class MinWindow:

    def minWindow(self, s, t):
        left = right = valid = start = 0  # 双指针 left 左指针 right: 右指针  valid：有效数量 start: 开始位置
        window = {}  # 窗口，字典，方便查询
        need = {}  # 将t的每一个字符存入字典中，value是这个字符出现的次数
        # start = 0
        end = sys.maxsize  # 结束位置，默认使用最大值
        for i in range(len(t)):  # 将t的每一个字符存入字典中，value是这个字符出现的次数
            if not need.get(t[i], False):
                need.update({t[i]: 1})

            else:
                need[t[i]] += 1
        while right < len(s):
            c = s[right]  # 取右侧窗口的第一个数
            right += 1  # 扩大窗口
            if need.get(c, False):  # 判断这个字符是否是在目标字符中
                if not window.get(c, False):  # 更新window的值
                    window.update(({c: 1}))
                else:
                    window[c] += 1
                if window[c] == need[c]:  # 如果这个窗口里的这个字符的数量也和t中相等了 , 则有valid + 1
                    valid += 1
            # 缩小窗口  窗口缩小条件判定
            while valid == len(need) and valid != 0:
                d = s[left]  # 最左侧字符
                if right - left < end:  # 判断是否是需要的区间, 并且区间大小一定要比上一个大小要小
                    start = left
                    end = right - left
                left += 1  # 缩小窗口
                if need.get(d, False):  # 当这个字符存在于need中
                    if need[d] == window[d]:  # 并且和window的值相等了
                        valid -= 1  # 有效数据valid -1
                    window[d] -= 1  # 当前window的这个值也 -1 (因为窗口缩小, 那么这个值就在窗口外了)
        return s[start:start + end] if end != sys.maxsize else ""


"""
    @:author Training
    @:description  438. 找到字符串中所有字母异位词
       给定一个字符串 s 和一个非空字符串 p，找到 s 中所有是 p 的字母异位词的子串，返回这些子串的起始索引。

        字符串只包含小写英文字母，并且字符串 s 和 p 的长度都不超过 20100。
       示例 1:

        输入:
        s: "cbaebabacd" p: "abc"
        
        输出:
        [0, 6]
        
        解释:
        起始索引等于 0 的子串是 "cba", 它是 "abc" 的字母异位词。
        起始索引等于 6 的子串是 "bac", 它是 "abc" 的字母异位词。
        
        来源：力扣（LeetCode）
        链接：https://leetcode-cn.com/problems/find-all-anagrams-in-a-string
        著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
    @:think 使用滑动窗口
    @:param  
    @:return 
"""


def findAnagrams(s: str, p: str) -> List[int]:
    left = 0
    l = len(p)
    right = 0
    window = {}
    need = {}
    res = []
    valid = 0
    for i in range(l):
        k = p[i]
        if k in need:
            need[k] += 1
        else:
            need[k] = 1
    while right < len(s):
        c = s[right]
        right += 1
        if c in need:
            if c in window:
                window[c] += 1
            else:
                window[c] = 1
            if window[c] == need[c]:
                valid += 1
        # 缩小窗口判定
        while right - left == l:
            if valid == len(need):
                res.append(left)
            d = s[left]
            left += 1
            if d in need:
                if d in window:
                    if need[d] == window[d]:
                        valid -= 1
                    window[d] -= 1
    return res


"""
    @:author Training
    @:description  
        122. 买卖股票的最佳时机 II
        给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
    
        设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
        
        注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
        
        来源：力扣（LeetCode）
        链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii
        著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
    @:think 
        (这个问题和股票问题1不一样的是: 1. 没有购买股票的次数限制 2. 在手里有股票的时候就不能购买了,必须抛出了才能再次买)
        (所以: 不用对比前一天的收益选最大值)
        从第一天买一个,当第二天的股票价格大于第二天则抛出, 以此循环到最后,如果第一天的价格小于第一天, 则不买
        此算法的意思差不多, 选最大值
    @:param  
    @:return 
"""


def maxProfit(prices: List[int]) -> int:
    size = len(prices)
    # 边缘判定
    if size <= 0:
        return 0
    # 初始化初始数据
    dp_i_0 = 0  # 最初未购买
    dp_i_1 = -sys.maxsize - 1  # 最初已购买
    temp = 0  # 临时数据 储存收益
    i = 0
    while i < size:
        dp_i_0 = max(dp_i_0, dp_i_1 + prices[i])  # 因为和第一题不一样,可以无限次数购买和售出 所以不用对比前一天数据  获取当前收益 和 当前售出后得到的收益 取最大值
        dp_i_1 = max(dp_i_1, temp - prices[i])  # 获取当前已有收益
        #  整体流程就是 : 当第二天的数据比今天大那就卖了再买 所以dp_i_1不会改变
        temp = dp_i_0
        i += 1
    return dp_i_0


"""
    @:author Training
    @:description  169. 多数元素
        给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。

        你可以假设数组是非空的，并且给定的数组总是存在多数元素。
        示例 1:

        输入: [3,2,3]
        输出: 3
        示例 2:
        
        输入: [2,2,1,1,1,2,2]
        输出: 2
        
    @:think 这题很简单  很容易就想到暴力的方法 从头循环到尾 找出出现次数最多的
        但是此题使用的分治法
    @:param  
    @:return 
"""


def majorityElement(nums):
    def getMax(lo, hi):
        if lo == hi: return nums[lo]
        mid = (hi - lo) // 2 + lo
        print(mid, lo, hi)
        left = getMax(lo, mid)
        right = getMax(mid + 1, hi)
        if left == right: return left
        left_con = sum(1 for i in range(lo, hi + 1) if nums[i] == left)
        right_con = sum(1 for i in range(lo, hi + 1) if nums[i] == right)
        return left if left_con > right_con else right

    return getMax(0, len(nums) - 1)


"""
    @:author Training
    @:description  53. 最大子序和 
        给定一个整数数组 nums ，
        找到一个具有最大和的连续子数组
        （子数组最少包含一个元素），返回其最大和。
        
        示例:
        
        输入: [-2,1,-3,4,-1,2,1,-5,4]
        输出: 6
        解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
        
    @:think 贪婪算法 , 分治算法
    @:param  nums : List[]
    @:return int
"""


# 贪心算法
# def maxSubArray(self, nums: List[int]) -> int:
#     result = -sys.maxsize
#     maxVal = 0
#     l = len(nums)
#     if l == 1:return nums[0]
#     for i in range(l):
#         maxVal += nums[i];
#         result = max(result,maxVal)
#         if maxVal < 0:
#             maxVal = 0
#     return result

# 分治算法
# 从中间一份为二
# 那么有三种可能:
#   1. 左侧最大值就是最大值
#   2. 右侧最大值就是最大值
#   3. 左右两侧都不是最大值, 最大值跨左侧与右侧,在中间
# 先计算左侧最大子串
# 再计算右侧最大子串
# 然后计算中间的最大子串
# 最后只需要对比左,中,右 即可
def maxSubArray(self, nums: List[int]) -> int:
    leg = len(nums)
    if leg == 1: return nums[0] # 递归结束条件
    mid = leg >> 1  # 位运算 相当于除2然后取整

    lmax = self.maxSubArray(nums[0:mid])  # 左侧最大连续子串和
    rmax = self.maxSubArray(nums[mid:leg])  # 右侧最大连续子串和

    lmax_sum = -sys.maxsize  # 初始化向左计算的最大值
    rmax_sum = -sys.maxsize  # 初始化向右计算的最大值

    temp = 0  # 初始化临时数据
    # 向左计算,计算出左边的最大连续子串值
    for i in range(mid - 1, -1, -1):
        temp += nums[i]
        lmax_sum = max(temp, lmax_sum)
    temp = 0
    # 向右计算, 计算右侧的最大连续子串值
    for i in range(mid, leg):
        temp += nums[i]
        rmax_sum = max(temp, rmax_sum)
    # 最终获取左侧和右侧和中间三者中连续子串值的最大值
    return max(lmax, rmax, lmax_sum + rmax_sum)
